Chaîne, chemin, cycle

Définitions  C haîne (chemin), longueur de chaîne, chaîne fermée, cycle

• Dans un graphe non orienté  \(G\) , une chaîne est une suite finie de sommets et d’arêtes \(s_0, a_1, s_1, a_2,s_2,\dots, a_n,s_n\)  telle que l’arête  \(a_k\) a pour extrémités les sommets  \(s_{k-1}\) et \(s_k\) .
  
• La longueur de la chaîne est le nombre d’arêtes parcourues (la chaîne  \(s_0, a_1, s_1, a_2,s_2,\dots, a_n,s_n\) est donc de longueur \(n\) ).
  
• Si les sommets  \(s_0\) et  \(s_n\) sont confondus, on parle de chaîne fermée et dans ce cas la longueur de   la chaîne  \(s_0, a_1, s_1, a_2,s_2,\dots, a_n,s_n\) est   `n-1` .
  
• Si toutes les arêtes d’une chaîne fermée sont distinctes, on dit qu’il s’agit d’un cycle.
  
• Dans le cas d’un graphe orienté, on utilise la chaîne appelée chemin et il faut faire attention de respecter le sens des arcs.
  

Remarque

Quand il n’y a pas d’ambiguïté (pas d’arêtes parallèles comme dans le problème des ponts de
Königsberg), on peut définir une chaîne en donnant simplement la suite de ses sommets ou de ses arêtes.